package main

func main() {

}

//   0        4
// 1   2    5   6
//   3	 	  7
//   8        12
// 9   10  13   14
//   11		 15
// 0 1 2 3 | 0 1 2 3
func regionsBySlashes(grid []string) int {
	N := len(grid)
	size := 4 * N * N

	uf := newUf(size)

	for i, s := range grid {
		for j, c := range s {
			idx := i*N + j
			if c == '\\' {
				uf.union(idx+0, idx+2)
				uf.union(idx+1, idx+3)
			} else if c == '/' {
				uf.union(idx+0, idx+1)
				uf.union(idx+2, idx+3)
			} else {
				uf.union(idx+0, idx+1)
				uf.union(idx+0, idx+2)
				uf.union(idx+0, idx+3)
			}

		}
	}

	return 0
}

type uf struct {
	parent []int
	count  int
}

func newUf(size int) *uf {
	parent := make([]int, size)
	for i := 0; i < size; i++ {
		parent[i] = i
	}

	return &uf{
		parent: parent,
		count:  size,
	}
}

func (u *uf) union(i, j int) {
	if i == j {
		return
	}

	pi := u.find(i)
	pj := u.find(j)

	if pi != pj {
		u.parent[i] = pj
		u.count--
	}
}

func (u *uf) find(i int) int {
	if u.parent[i] == i {
		return i
	}

	return u.find(u.parent[i])
}
